Corelab Seminar
2020-2021
Andreas Galanis
The complexity of approximating averages: phase transitions and complex dynamics
Abstract.
Given a graph G, can we approximate the average size of an independent set of G?
More generally, what determines the complexity of computing averages in Gibbs distributions (such as the Ising model)?
These questions are closely related to the complexity of evaluating the underlying polynomials, known as partition functions.
We will overview connections between the approximability of partition functions and phase transitions/complex dynamics,
and discuss how to obtain strong inapproximability results for computing averages.